Sum of Dependencies in a graph

Given a directed and connected graph with n nodes.
If there is an edge from u to v then u depends on v.

Find the sum of dependencies for every node.

Example

A depends on C and D
B depends on D
C depends on D
D depends on none
So answer is 2 + 1 + 1 = 4



In [1]:

    
class Graph():
    def __init__(self, size):
        self.data = []
        for i in xrange(size):
            self.data.append([])
            
    def addEdge(self, u, v):
        self.data[u].append(v)
        
    def sum_of_dependencies(self):
        count = 0
        for i in self.data:
            count += len(i)
        return count



In [2]:

    
g = Graph(4)
print g.data









    



[[], [], [], []]



In [3]:

    
g.addEdge(0, 2)
g.addEdge(0, 3)
g.addEdge(1, 3)
g.addEdge(2, 2)
print g.data









    



[[2, 3], [3], [2], []]



In [4]:

    
print g.sum_of_dependencies()

Resources

http://www.geeksforgeeks.org/sum-dependencies-graph/